package leetcode.code;

import java.util.*;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @author : zx
 * @version V1.0
 */
public class Code {

    public static boolean isStraight1(Integer[] nums) {
        if(nums == null || nums.length != 5) return false;
        Arrays.sort(nums, ( Integer a, Integer b) -> { return a-b;});
        int anyNums = 0;
        int pre = 0;
        boolean flag = false;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != 0) flag = true;
            if(flag){

                if(pre != 0){
                    if(nums[i]-pre == 0) return false;
                    anyNums -= (nums[i]-pre)-1;
                }
                pre = nums[i];
            }else{
                anyNums ++;
            }
            if(anyNums < 0) return false;
        }
        return true;
    }

    public static boolean isStraight(int[] nums) {
        return isStraight1(Arrays.stream(nums).boxed().toArray(Integer[]::new));
    }

    public static String minNumber(int[] nums) {
        StringBuilder sb = new StringBuilder();
        String[] s = new String[nums.length];
        for(int i = 0; i < s.length; i++){
            s[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(s, new Comparator<String>(){

            @Override
            public int compare(String s1, String s2){
                int maxSize = Math.max(s1.length(), s2.length());
                for(int i = 0; i < maxSize; i++){
                    if(s1.length()-1 < i){
                        if(s1.charAt(s1.length()-1) != s2.charAt(i)) return s1.charAt(s1.length()-1)-s2.charAt(i);
                    }else if(s2.length()-1 < i){
                        if(s1.charAt(s1.length()-i-1) != s2.charAt(0)) return s1.charAt(i)-s2.charAt(s2.length()-1);
                    }else{
                        if(s1.charAt(i) != s2.charAt(i)) return s1.charAt(i) - s2.charAt(i);
                    }
                }
                return 0;
            }

        });

        for(String i : s){
            sb.append(i);
        }
        return sb.toString();
    }

//    public static void main(String[] args){
//
////        简单题 s = new 简单题();
////        System.out.println(s.prisonAfterNDays(new int[]{1,0,0,1,0,0,1,0},
////        1000000000));
////        int[] a = new int[]{4,7,5,9,2};
////        System.out.println(isStraight(a));
////
////        Queue<Integer> set = new LinkedList<Integer>();
////
////        set.add(1);
////        set.add(2);
////        set.add(3);
////        System.out.println(set.toString());
//
//        Scanner scanner = new Scanner(System.in);
//        while(scanner.hasNext()){
//            int N = scanner.nextInt();
//            int M = scanner.nextInt();
//            int[] dp = new int[M-N+1];
//            for(int i = 2; i < dp.length; i++){ // i:到达
//                for(int j = i; j >= 2; j--){ // j:约数
//                    if((N+i-j)%j==0 && j!=(N+i-j)){
//                        if(i == j) dp[i] = 1;
//                        else{
//                            if(dp[i-j] != 0) dp[i] = dp[i]==0 ? dp[i-j]+1 : Math.min(dp[i], dp[i-j]+1);
//                        }
//                    }
//                }
//            }
//            System.out.println(dp[M-N]);
//
//        }
//        scanner.close();
//
//    }

    public static void main(String[] args){
//        System.out.println(minNumber(new int[]{20, 2, 1}));
//        System.out.println(singleNumber(new int[]{3, 3 ,3 ,4}));
        System.out.println(coinChange(new int[]{500, 401, 1}, 802));
    }

    public static int singleNumber(int[] nums) {
        int[] bits = new int[32];
        for(int i : nums){
            int z = 0;
            while(z < 32){
                if((i & (0x1<<z))!= 0) bits[z]++;
                z++;
            }
        }
        int res = 0;
        for(int i = 0; i < bits.length; i++){
            if(bits[i] % 3 != 0){
                res += 0x1 << i;
            }
        }
        return res;
    }

    public static int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        return isLegal(coins, coins.length-1, 0, amount);
    }

    private static int isLegal(int[] coins, int index, int sum, int amount){
        if(index < 0){
            return sum==amount ? 0 : -1;
        }
        else{
            int n = (amount-sum)/coins[index];
            for(int i = n; i >= 0; i--){
                int r = isLegal(coins, index-1, sum+coins[index]*i, amount);
                if(r >= 0) return i+r;
            }
        }
        return -1;
    }


    public static class TestABC{

        private static int state = 1;
        private static int count = 30 * 3;
        private static final Lock lock = new ReentrantLock();

        public static void run(){
            Thread a = new Thread(new Runnable() {
                @Override
                public void run() {
                    while(count >= 0){
                        lock.lock();
                        if(state % 3 == 1){
                            System.out.println("A");
                            state=2;
                            count--;
                        }

                        lock.unlock();
                    }
                }
            });
            Thread b = new Thread(new Runnable() {
                @Override
                public void run() {
                    while(count >= 0){
                        lock.lock();
                        if(state % 3 == 2){
                            System.out.println("B");
                            state=3;
                            count--;
                        }

                        lock.unlock();
                    }
                }
            });
            Thread c = new Thread(new Runnable() {
                @Override
                public void run() {
                    while(count >= 0){
                        lock.lock();
                        if(state % 3 == 0){
                            System.out.println("C");
                            state=1;
                            count--;
                        }

                        lock.unlock();
                    }
                }
            });
            a.start();
            b.start();
            c.start();
        }

    }
}
